Mặc dù hai quốc gia có ít mối liên hệ do vị trí địa lý khác biệt, nhưng hai quốc gia dù sao cũng có chung một lịch sử tương tự: họ có một số lịch sử lâu đời nhất và lâu đời nhất ở Châu Âu và Châu Á. Cả Ba Lan và Việt Nam đều được công nhận vì đã đánh bại hai đế chế hùng mạnh trong lịch sử tương ứng của họ, đế chế Ottoman và Mông Cổ và cứu từng lục địa khỏi các mối đe dọa của các đế chế này. Cả hai cũng đóng góp một số nhân vật nổi tiếng, lôi cuốn và đáng kính nhất trong lịch sử tương ứng của họ: như John III Sobieski, Józef Piłsudski, Józef Poniatowski, Witold Pilecki, Tadeusz Kościuszko, Casimir Pulaski, và Ngô Quyền, Trần Hưng Đạo, Võ Nguyên Giáp, Phan Bội Châu, Hai Bà Trưng, ​​Nguyễn An, Lý Long Tường cho Việt Nam. Một số trong những số liệu này cũng được tôn kính bên ngoài cả hai quốc gia như Urbanowicz ở Anh, Pulaski và Kościuszko cho Hoa Kỳ; Lý Long Tường ở Hàn Quốc và Nguyễn An ở Trung Quốc. Vào thế kỷ 17, nhà truyền giáo Dòng Tên Ba Lan Wojciech Męciński đã đến thăm Việt Nam.

Hai nước bắt đầu thiết lập ngoại giao vào năm 1950[1], và sau đó đã thăng tiến dần khi hai nước vẫn còn đang là những nước cộng sản[2][3]. Việt Nam đã nhận được sự đồng cảm rất lớn của đồng nghiệp Ba Lan khi họ đến Bắc Việt Nam vào những năm 1960 do sự tương đồng về lịch sử của họ; và những người nhập cư Việt Nam đến Ba Lan cũng cảm nhận Ba Lan theo cách tương tự do lịch sử của Ba Lan sở hữu. Khi Việt Nam chịu sự lên án và cấm vận toàn cầu do Hoa Kỳ và Trung Quốc lãnh đạo trong cuộc chiến tranh chống Campuchia của Khmer Đỏ, Ba Lan, cả Chính phủ và phong trào Đoàn kết chống cộng, là một trong số ít các quốc gia thể hiện tình đoàn kết với Việt Nam về chiến tranh, một hành động góp phần vào Cộng hòa Ba Lan thứ ba sau này, vào những năm 1990, để triển khai quân đội đến Campuchia theo nhiệm vụ của Liên Hợp Quốc giúp ổn định Campuchia. Năm 1946, người sáng lập tương lai của Israel, một người Do Thái Ba Lan, David Ben-Gurion, đã gặp Hồ Chí Minh tại Paris. Mong muốn thành lập Israel và ấn tượng lịch sử từ Hồ Chí MInh đến Ba Lan được coi là mối ràng buộc không chính thức đầu tiên giữa Việt Nam và Ba Lan. Quan hệ ngoại giao chính thức được thiết lập vào năm 1950. Janusz Lewandowski, đại diện phái đoàn Ba Lan trong Hiệp định Genève năm 1954, đã phản đối ý tưởng tách Việt Nam thành hai phần do Chính phủ Cộng hòa Nhân dân Trung Hoa mới thành lập. Quan hệ của Ba Lan Việt Nam phát triển từ các chương trình trao đổi sinh viên những năm 1950 và 1980, trong thời gian đó cả Ba Lan và Việt Nam

Đặc phái viên Ba Lan, Janusz Lewandowski, người đã có mặt trong Hiệp định Genève năm 1954, phản đối quyết liệt việc phân chia Việt Nam làm hai miền mà chính phủ Trung Quốc do Chu Ân Lai đề xuất.

Một lượng lớn kỹ sư Ba Lan tới Việt Nam trong thời kỳ Chiến tranh Việt Nam và họ đã có những ghi chép cho thấy ấn tượng sâu sắc về người Việt cũng như ý chí người Việt, đã cảm thông sâu sắc và nhiều lần so sánh với các cuộc nổi dậy và các cuộc chiến đòi độc lập của người Ba Lan chống lại ách cai trị của Nga và Đức.

Sau khi Liên Xô tan rã năm 1991, quan hệ giữa hai nước đã không mấy tiến triển, do những khác biệt về sau và việc Ba Lan từ bỏ chủ nghĩa Cộng sản đã làm quan hệ hai nước đóng băng. Chỉ đến những năm 2000, hai nước mới lại nồng ấm lên về ngoại giao.